package nextoffer;

/**
 * @author ：szq
 * @date ：Created in 2022/3/16 10:58
 * @description：12. 矩阵中的路径
 * @modified By：
 * @version: $
 */
public class thePathInTheMatrix {
    int[][] visit = new int[200][200];
    String word ;
    int n,m;
    char[][] board;
    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.n = board.length;
        this.m = board[0].length;
        this.word = word;
        for(int i = 0 ; i < board.length;i++)
        {
            for(int j = 0; j  < board[i].length;j++)
            {
                if(board[i][j] == word.charAt(0))
                {
                    if(dfs(i,j,0))return  true;
                }
            }
        }
        return false;
    }

    public boolean dfs(int i,int j,int l )
    {
        if(l==word.length())return  true;
        if(i<0||i>=n||j>0||j>=m||visit[i][j]==1||word.charAt(l)!=board[i][j])
            return false;
        visit[i][j] = 1; //标记深搜
        //CAA
        //AAA
        //BCD
        boolean res = dfs(i+1,j,l+1)||
                dfs(i,j+1,l+1)||
                dfs(i-1,j,l+1)||
                dfs(i,j-1,l+1);

        visit[i][j] = 0; //像这个例子 只能从中间才能找到，中间第一个走过来需要回溯
        //CAA
        //AAA
        //BCD
        return res;
    }



}
